{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "broadband-zealand",
   "metadata": {},
   "source": [
    "# Python 数据结构"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adjustable-newsletter",
   "metadata": {},
   "source": [
    "顾名思义，数据结构是能够将数据组合在一起的一种结构。\n",
    "\n",
    "在数据科学领域，很多情况下需要将数据进行有序排列。例如我们统计了大学某班 50 人的数学成绩，那么创建 50 个变量例如 XiaoMing = 99, XiaoHu = 86 .... 无疑是非常繁琐的。这时我们可以通过数据结构整合这些数据，例如在上一节中以方括号标识的序列 \\[ 99, 86, 77 .... \\]，这将会使我们的程序大大简化。\n",
    "\n",
    "Python 中常用的数据结构有：\n",
    "\n",
    "- 序列 List: 用于保存有序项集合的变量，以方括号标识。\n",
    "- 元组 Tuple: 用于保存有序项集合的常量，以圆括号标识。\n",
    "- 字典 Dict: 用于保存无序（键，值）项集合的变量，以花括号标识。\n",
    "- 集合 Set: 用于保存无序项集合的变量，以花括号标识。\n",
    "\n",
    "瑞士计算机科学家 Niklaus Wirth 曾说过 \"程序 = 数据结构 + 算法\"，这个公式在 40 年后的今天仍然成立。掌握 Python 中常用的数据结构是我们设计程序的一大基石。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "obvious-strength",
   "metadata": {},
   "source": [
    "> 在本节中我们将尝试设计一个学生成绩管理系统，实现对学生成绩的增、删、查、改功能。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "according-admission",
   "metadata": {},
   "source": [
    "## 1.2.1 序列"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "union-medication",
   "metadata": {},
   "source": [
    "序列是用于保存有序项集合的变量，通过方括号创建。序列是最容易理解的数据结构，它就像一个任务清单，任务清单的每一项都是一个单独的任务。\n",
    "\n",
    "下面我们创建一个含有四个整数的列表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "entertaining-setting",
   "metadata": {},
   "outputs": [],
   "source": [
    "l = [1, 2, 3, 4]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "through-reconstruction",
   "metadata": {},
   "source": [
    "\n",
    "序列支持以下操作：\n",
    "\n",
    "- 增：通过函数 append 可以向序列内增加元素\n",
    "- 删：通过关键字 del 可以删除序列内元素\n",
    "- 查：通过关键字 \\[ \\] 可以查找序列某个位置元素\n",
    "- 改：通过赋值符号 = 可以修改某个位置的元素\n",
    "\n",
    "序列的优点是：\n",
    "\n",
    "- 快速向尾部添加元素\n",
    "- 快速遍历所有元素\n",
    "- 节省占用计算机内容空间"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "expired-chase",
   "metadata": {},
   "source": [
    "### 1.2.1.1 查找元素"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "stretch-newsletter",
   "metadata": {},
   "source": [
    "我们通过 \\[ \\] 关键字查找序列中某个位置的元素。\n",
    "\n",
    "例如 l\\[0\\] 可以获取序列中首个元素，l\\[2\\] 可以获取序列中第 2 个元素。同时它还支持倒序查找，例如 l\\[-1\\] 表示倒数第一个元素（末尾的元素）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "covered-douglas",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "4\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "## 查找 首个 元素\n",
    "print(l[0])\n",
    "## 查找第 2 个元素\n",
    "print(l[2])\n",
    "## 查找第 最后 元素\n",
    "print(l[-1])\n",
    "## 查找倒数第 2 个元素\n",
    "print(l[-2])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "photographic-worker",
   "metadata": {},
   "source": [
    "\\[ \\] 关键字也可以通过 “切片” 的形式获取含有多个元素的子序列。\n",
    "\n",
    "例如 l\\[ 0 \\: 2 \\] 代表序列从中第 0 个元素 到 第 2 个元素（前开后闭，不包括第 2 个元素）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "informative-national",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2]\n",
      "[2, 3]\n"
     ]
    }
   ],
   "source": [
    "## 查找第 0 到 第 2 的元素子序列\n",
    "print(l[0:2])\n",
    "## 查找第 1 到 最后 的元素子序列\n",
    "print(l[1:-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bronze-brook",
   "metadata": {},
   "source": [
    "### 1.2.1.2 修改元素"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alien-appeal",
   "metadata": {},
   "source": [
    "通过 \\[ \\] 关键字同样可以修改序列中某个位置的元素，类似的它也支持倒序以及切片的形式。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "verbal-writing",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-1, 2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "## 修改 首个 元素的值为 -1\n",
    "l[0] = -1\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "eastern-royalty",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-1, -2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "## 修改从第 0 到第 2 的元素子序列的值为 [-1, -2]\n",
    "l[0:2] = [-1, -2]\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "trained-saskatchewan",
   "metadata": {},
   "source": [
    "### 1.2.1.3 增加元素"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "political-astrology",
   "metadata": {},
   "source": [
    "通过 append 函数可以实现向序列尾部添加新的元素。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "unavailable-chosen",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-1, -2, 3, 4, 5]\n",
      "[-1, -2, 3, 4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "## 向集合尾部添加元素 5\n",
    "l.append(5)\n",
    "print(l)\n",
    "## 向集合尾部添加元素 6\n",
    "l.append(6)\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hundred-ability",
   "metadata": {},
   "source": [
    "### 1.2.1.4 删除元素"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "similar-delhi",
   "metadata": {},
   "source": [
    "通过 del 关键字可以删除序列某个位置的元素。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "female-temple",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-2, 3, 4, 5, 6]\n",
      "[-2, 3, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "## 删除序列 首个 元素\n",
    "del l[0]\n",
    "print(l)\n",
    "## 删除序列 最后一个 元素\n",
    "del l[-1]\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "better-architect",
   "metadata": {},
   "source": [
    "### 1.2.1.5 小例子"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "correct-coalition",
   "metadata": {},
   "source": [
    "在熟悉了序列的增删查找功能后，我们就可以尝试以此为基础搭建我们的学生成绩管理系统。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "front-consequence",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "<blockquote>\n",
    "\n",
    "Task 1. 在上一次期末考试中，XiaoHu 考了数学 65 分，语文 55 分；XiaoMing 考了数学 80 分，语文92 分；XiaoWei 考了数学 95 分，语文 98 分，以此建立学生成绩管理系统。\n",
    "\n",
    "Task 2. 在本次期末考试中，XiaoHu 考了数学 95 分，语文 85 分；XiaoMing 考了数学 75 分，语文 71 分；XiaoWei 考了数学 92 分，语文 93 分，以此对之前的成绩进行更新。\n",
    "\n",
    "Task 3. 由于 XiaoMing 的成绩出现了大幅度下滑，家长决定要 XiaoMing 转学到另一所高中，以此在系统中删除 XiaoMing 的信息。\n",
    "\n",
    "Task 4. 学校新转来的学生 Cryin 本次考试成绩为 数学 87 分，语文 88 分，在系统中录入 Cryin 的成绩。\n",
    "\n",
    "</blockquote>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "powerful-flower",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Task 1 建立学生信息管理系统\n",
    "\n",
    "## 首先建立一个 “名字” 序列记录哪个学生在序列的哪个位置。\n",
    "names = ['XiaoHu', 'XiaoMing', 'XiaoWei']\n",
    "\n",
    "## 根据名字序列的位置分别建立 “语文成绩” “数学成绩序列” 序列。\n",
    "math_scores = [65, 80, 95]\n",
    "language_scores = [55, 92, 98]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "handled-throat",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Task 2 根据本次期末考试的成绩更新系统\n",
    "\n",
    "## 首先找到 \"XiaoHu\" 在哪个位置，更新该位置的成绩\n",
    "## 通过 for-in 循环遍历名字元素\n",
    "position = -1\n",
    "count = 0\n",
    "for name in names:\n",
    "    ## 找到 XiaoHu 在序列中的位置\n",
    "    if name == \"XiaoHu\":\n",
    "        position = count\n",
    "    count = count + 1\n",
    "## 根据 XiaoHu 在序列中的位置更新成绩\n",
    "math_scores[position] = 95\n",
    "language_scores[position] = 85\n",
    "\n",
    "## 以同样方法更新 XiaoMing 与 XiaoWei 的成绩\n",
    "position = -1\n",
    "count = 0\n",
    "for name in names:\n",
    "    if name == \"XiaoMing\":\n",
    "        position = count\n",
    "    count = count + 1\n",
    "math_scores[position] = 75\n",
    "language_scores[position] = 71\n",
    "\n",
    "position = -1\n",
    "count = 0\n",
    "for name in names:\n",
    "    if name == \"XiaoWei\":\n",
    "        position = count\n",
    "    count = count + 1\n",
    "math_scores[position] = 92\n",
    "language_scores[position] = 93"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "expensive-assembly",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['XiaoHu', 'XiaoMing', 'XiaoWei']\n",
      "[95, 75, 92]\n",
      "[85, 71, 93]\n"
     ]
    }
   ],
   "source": [
    "print(names)\n",
    "print(math_scores)\n",
    "print(language_scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "healthy-blood",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Task 3 删除 XiaoMing 的信息\n",
    "\n",
    "## 首先找到 \"XiaoMing\" 在哪个位置\n",
    "## 通过 for-in 循环遍历名字元素\n",
    "position = -1\n",
    "count = 0\n",
    "for name in names:\n",
    "    ## 找到 XiaoMing 在序列中的位置\n",
    "    if name == \"XiaoMing\":\n",
    "        position = count\n",
    "    count = count + 1\n",
    "## 根据 XiaoMing 在序列中的位置删除\n",
    "del names[position]\n",
    "del math_scores[position]\n",
    "del language_scores[position]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "olive-plumbing",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['XiaoHu', 'XiaoWei']\n",
      "[95, 92]\n",
      "[85, 93]\n"
     ]
    }
   ],
   "source": [
    "print(names)\n",
    "print(math_scores)\n",
    "print(language_scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "homeless-bangladesh",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Task 4 录入 Cryin 的信息\n",
    "\n",
    "names.append('Cryin')\n",
    "math_scores.append(87)\n",
    "language_scores.append(88)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "european-encounter",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['XiaoHu', 'XiaoWei', 'Cryin']\n",
      "[95, 92, 87]\n",
      "[85, 93, 88]\n"
     ]
    }
   ],
   "source": [
    "print(names)\n",
    "print(math_scores)\n",
    "print(language_scores)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "confident-utility",
   "metadata": {},
   "source": [
    "以上我们就初步实现了学生成绩管理系统，并实现了用户的一些简单需求。可以发现序列的增删改操作相对轻松，但最困难的部分是需要遍历整个序列寻找元素在序列中的位置，这种困难是由序列在计算机中的存储形式决定的。后面我们介绍的数据结构 “字典” 可以用来解决这个问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alien-magnitude",
   "metadata": {},
   "source": [
    "## 1.2.2 元组"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "composed-sigma",
   "metadata": {},
   "source": [
    "元组与列表具有近乎一样的特性，他们唯一的区别在于元组无法被修改。由于不可修改的特性，元组一般用来保证存放数据的可靠性，例如用元组保存八大行星的名称，因为它们的名称不会被改变，也不会轻易减少： \n",
    "\n",
    "    planets = [ Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune]\n",
    "\n",
    "下面我们创建一个含有四个元素的元组。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "welcome-philippines",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = (1, 2, 3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "vocal-regard",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'tuple' object does not support item assignment",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-46-1c5494cdb28c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m## 尝试修改元组，提示元素无法被赋值\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mt\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: 'tuple' object does not support item assignment"
     ]
    }
   ],
   "source": [
    "## 尝试修改元组，提示元素无法被赋值\n",
    "\n",
    "t[0] = -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "friendly-designation",
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'tuple' object has no attribute 'append'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-47-5b52b45d5bf4>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m## 尝试增加元素，系统提示不支持 append 操作\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mt\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m: 'tuple' object has no attribute 'append'"
     ]
    }
   ],
   "source": [
    "## 尝试增加元素，系统提示不支持 append 操作\n",
    "t.append(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "acceptable-denver",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'tuple' object doesn't support item deletion",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-48-3ab29490507d>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m## 尝试删除元素，系统提示元素无法被删除\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32mdel\u001b[0m \u001b[0mt\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: 'tuple' object doesn't support item deletion"
     ]
    }
   ],
   "source": [
    "## 尝试删除元素，系统提示元素无法被删除\n",
    "del t[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "frank-myanmar",
   "metadata": {},
   "source": [
    "## 1.2.3 字典"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "prescribed-receptor",
   "metadata": {},
   "source": [
    "顾名思义，字典就像现实世界中的字典，只要知道一个单词的读音，就能找到它在书中具体的位置！即我们将一个 “键(key)” 与 “值(value)” 相关联，通过键迅速检索到对应的值。要注意键必须是唯一的，这就好比两个单词如果读音一样就会出现歧义一样。\n",
    "\n",
    "字典通过花括号 \\{ \\} 创建，通过 : 符号区分键与值，通过逗号分隔。下面我们创建一个字典存储联系人的邮箱。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "formal-policy",
   "metadata": {},
   "outputs": [],
   "source": [
    "ab = {\n",
    "    \"XiaoHu\": \"xiaohu@RNG.com\",\n",
    "    \"XiaoWei\": \"xiaowei@RNG.com\",\n",
    "    \"XiaoMing\": \"xiaoming@RNG.com\"\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "discrete-sequence",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'XiaoHu': 'xiaohu@RNG.com', 'XiaoWei': 'xiaowei@RNG.com', 'XiaoMing': 'xiaoming@RNG.com'}\n"
     ]
    }
   ],
   "source": [
    "print(ab)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hourly-brick",
   "metadata": {},
   "source": [
    "字典支持以下操作：\n",
    "- 增：通过关键字 \\[ \\] 可以向序列内增加元素\n",
    "- 删：通过关键字 del 可以删除序列内元素\n",
    "- 查：通过关键字 \\[ \\] 可以查找序列某个位置元素\n",
    "- 改：通过赋值符号 = 可以修改某个位置的元素\n",
    "\n",
    "字典的优点是：\n",
    "- 快速检索到键对应的值\n",
    "- 字典内的键值不存在顺序关系"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "revolutionary-remainder",
   "metadata": {},
   "source": [
    "### 1.2.3.1 增加元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "patient-investment",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'XiaoHu': 'xiaohu@RNG.com', 'XiaoWei': 'xiaowei@RNG.com', 'XiaoMing': 'xiaoming@RNG.com', 'Cryin': 'cryin@RNG.com'}\n"
     ]
    }
   ],
   "source": [
    "## 通过 [ ] 关键字 与赋值符号 = 向字典添加新的元素\n",
    "\n",
    "ab['Cryin'] = \"cryin@RNG.com\"\n",
    "print(ab)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "active-fellowship",
   "metadata": {},
   "source": [
    "### 1.2.3.2 删除元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "bigger-celebrity",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'XiaoHu': 'xiaohu@RNG.com', 'XiaoWei': 'xiaowei@RNG.com', 'Cryin': 'cryin@RNG.com'}\n"
     ]
    }
   ],
   "source": [
    "## 通过 del 关键字 删除字典中的元素\n",
    "\n",
    "del ab['XiaoMing']\n",
    "print(ab)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "still-sitting",
   "metadata": {},
   "source": [
    "### 1.2.3.3 查找元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "outdoor-processor",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "xiaohu@RNG.com\n"
     ]
    }
   ],
   "source": [
    "## 通过 [ ] 关键字根据键查找值\n",
    "\n",
    "print(ab['XiaoHu'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "informational-tournament",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 通过 in 关键字可以查找某个键是否在字典中\n",
    "print('XiaoHu' in ab)\n",
    "print('UZI' in ab)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "neither-barrier",
   "metadata": {},
   "source": [
    "### 1.2.3.4 修改元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "interstate-russia",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'XiaoHu': 'xiaohu@EDG.com', 'XiaoWei': 'xiaowei@RNG.com', 'Cryin': 'cryin@RNG.com'}\n"
     ]
    }
   ],
   "source": [
    "## 通过 [ ] 关键字 与赋值符号 = 修改字典内的元素\n",
    "\n",
    "ab['XiaoHu'] = \"xiaohu@EDG.com\"\n",
    "print(ab)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "supported-probe",
   "metadata": {},
   "source": [
    "### 1.2.3.5 小例子"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "narrative-postage",
   "metadata": {},
   "source": [
    "下面我们以字典为基础重新构建学生成绩管理系统："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "fitted-trade",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'XiaoHu': 65, 'XiaoMing': 80, 'XiaoWei': 95}\n",
      "{'XiaoHu': 55, 'XiaoMing': 92, 'XiaoWei': 98}\n"
     ]
    }
   ],
   "source": [
    "## Task 1 建立学生信息管理系统\n",
    "\n",
    "math_scores = {}\n",
    "math_scores['XiaoHu'] = 65\n",
    "math_scores['XiaoMing'] = 80\n",
    "math_scores['XiaoWei'] = 95\n",
    "\n",
    "language_scores = {}\n",
    "language_scores['XiaoHu'] = 55\n",
    "language_scores['XiaoMing'] = 92\n",
    "language_scores['XiaoWei'] = 98\n",
    "\n",
    "print(math_scores)\n",
    "print(language_scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "regular-jackson",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'XiaoHu': 95, 'XiaoMing': 75, 'XiaoWei': 92}\n",
      "{'XiaoHu': 85, 'XiaoMing': 71, 'XiaoWei': 93}\n"
     ]
    }
   ],
   "source": [
    "## Task 2 根据本次期末考试的成绩更新系统\n",
    "\n",
    "math_scores['XiaoHu'] = 95\n",
    "math_scores['XiaoMing'] = 75\n",
    "math_scores['XiaoWei'] = 92\n",
    "\n",
    "language_scores = {}\n",
    "language_scores['XiaoHu'] = 85\n",
    "language_scores['XiaoMing'] = 71\n",
    "language_scores['XiaoWei'] = 93\n",
    "\n",
    "print(math_scores)\n",
    "print(language_scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "global-orleans",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'XiaoHu': 95, 'XiaoWei': 92}\n",
      "{'XiaoHu': 85, 'XiaoWei': 93}\n"
     ]
    }
   ],
   "source": [
    "## Task 3 删除 XiaoMing 的信息\n",
    "\n",
    "del math_scores['XiaoMing']\n",
    "del language_scores['XiaoMing']\n",
    "\n",
    "print(math_scores)\n",
    "print(language_scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "golden-composition",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'XiaoHu': 95, 'XiaoWei': 92, 'Cryin': 87}\n",
      "{'XiaoHu': 85, 'XiaoWei': 93, 'Cryin': 88}\n"
     ]
    }
   ],
   "source": [
    "## Task 4 录入 Cryin 的信息\n",
    "\n",
    "math_scores['Cryin'] = 87\n",
    "language_scores['Cryin'] = 88\n",
    "\n",
    "print(math_scores)\n",
    "print(language_scores)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "maritime-victim",
   "metadata": {},
   "source": [
    "在我们的小例子中可以观察到，字典构建的学生管理系统避免了查找元素所在位置的操作，这是字典根据“键”可以迅速找到“值”的特性决定的。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "nominated-transaction",
   "metadata": {},
   "source": [
    "## 1.2.4 集合"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "minus-anchor",
   "metadata": {},
   "source": [
    "集合是用来存储无序的元素集合。通常我们只考虑元素的存在，而不考虑元素的顺序或出现次数时使用集合。\n",
    "\n",
    "集合与字典一样也通过花括号创建，但不存在 : 分隔符号。例如用集合表示中国的四个直辖市，它们无需考虑顺序与出现次数。\n",
    "\n",
    "    municipalities = { \"Beijing\", \"Shanghai\", \"Tianjin\", \"Chongqing\" }\n",
    "\n",
    "注意集合中不能存在重复元素。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "imported-destruction",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 创建一个集合\n",
    "\n",
    "s = {1,2,3,4,5}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "stopped-logging",
   "metadata": {},
   "source": [
    "集合支持以下操作：\n",
    "- 增：通过函数 add 可以向集合内增加元素\n",
    "- 删：通过函数 remove 可以删除集合内元素\n",
    "- 查：通过关键字 in 可以查找某个元素是否在集合内\n",
    "\n",
    "集合的优点是：\n",
    "- 支持数学集合操作\n",
    "- 快速检索某个元素是否在集合内\n",
    "- 集合内的键值不存在顺序关系"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "welcome-church",
   "metadata": {},
   "source": [
    "### 1.2.4.1 增加元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "unlike-thermal",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 5, 6}\n"
     ]
    }
   ],
   "source": [
    "## 增加新的元素到集合中\n",
    "\n",
    "s.add(6)\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "focused-aberdeen",
   "metadata": {},
   "source": [
    "### 1.2.4.2 删除元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "mounted-pioneer",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 5}\n"
     ]
    }
   ],
   "source": [
    "## 删除集合中某个元素\n",
    "\n",
    "s.remove(6)\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fitted-ceiling",
   "metadata": {},
   "source": [
    "### 1.2.4.3 查找元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "coordinated-pillow",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "## 查找某个元素是否在集合中\n",
    "print(5 in s)\n",
    "print(6 in s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "animated-prevention",
   "metadata": {},
   "source": [
    "### 1.2.4.4 数学操作"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "touched-harvard",
   "metadata": {},
   "source": [
    "集合的一大特点是支持数学操作，其中包括求集合的 并集、交集 以及 亦或 操作。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "motivated-yesterday",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 创建另一个集合\n",
    "s2 = {3,4,5,6,7}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "affiliated-setup",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 5, 6, 7}\n"
     ]
    }
   ],
   "source": [
    "## 集合并集\n",
    "print(s | s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "disabled-enzyme",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{3, 4, 5}\n"
     ]
    }
   ],
   "source": [
    "## 集合交集\n",
    "print(s & s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "healthy-paradise",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 6, 7}\n"
     ]
    }
   ],
   "source": [
    "## 集合亦或\n",
    "print(s ^ s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "burning-contact",
   "metadata": {},
   "source": [
    "## 1.2.5 练习"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "static-framework",
   "metadata": {},
   "source": [
    "### 1.2.5.1 序列练习"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "previous-basin",
   "metadata": {},
   "source": [
    "<blockquote>\n",
    "给定两个大小分别为 m 和 n 的升序（从小到大）序列 nums1 和 nums2。请你找出并返回这两个升序序列的 中位数 。\n",
    "\n",
    "例子：\n",
    "    \n",
    "    输入：nums1 = [1,2], nums2 = [3,4]\n",
    "    输出：2.50000\n",
    "    解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5\n",
    "</blockquote>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "instrumental-melbourne",
   "metadata": {},
   "source": [
    "找到两个序列的中位数的思路分两步，首先合并两个升序序列为一个升序序列，然后找到升序序列中中间的数即为中位数。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "express-insulin",
   "metadata": {},
   "source": [
    "合并两个升序序列的思路很简单，因为两个序列都是升序，所以只需要判断两个序列首个元素的大小，将最小的依次放入一个新的数组中。如果其中一个数组空了，说明另一个数组中的所有元素都比之前的大，将它们合并到新数组的尾部即可。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "mysterious-fairy",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 定义合并两个升序序列的函数\n",
    "def merge(nums1, nums2):\n",
    "    result = []\n",
    "    ## 如果两个序列都不是空的，依次比较首个元素大小\n",
    "    while len(nums1) > 0 and len(nums2) > 0:\n",
    "        ## 如果第一个序列首个元素更小\n",
    "        if nums1[0] < nums2[0]:\n",
    "            ## 将 nums1 序列的首个元素放入 result 序列\n",
    "            result.append(nums1[0])\n",
    "            nums1 = nums1[1:]\n",
    "        ## 如果第 nums2 序列首个元素更小\n",
    "        else:\n",
    "            ## 将 nums2 序列的首个元素放入 result 序列\n",
    "            result.append(nums2[0])\n",
    "            nums2 = nums2[1:]\n",
    "    ## 如果某个序列空了，将非空的数组合并到 result 尾部\n",
    "    result = result + nums1\n",
    "    result = result + nums2\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "extraordinary-contract",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 在合并后的序列中寻找中位数\n",
    "def find_medium(nums):\n",
    "    half = len(nums) // 2\n",
    "    ## 如果序列长度为偶数，则取中间两个数的平均值\n",
    "    if len(nums) % 2 == 0:\n",
    "        return (nums[half - 1] + nums[half]) / 2\n",
    "    ## 如果序列长度为奇数，则取最中间数\n",
    "    else:\n",
    "        return nums[half]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "metric-natural",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.5"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_medium(merge(nums1, nums2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alpha-factory",
   "metadata": {},
   "source": [
    "### 1.2.5.2 字典练习"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "forbidden-family",
   "metadata": {},
   "source": [
    "<blockquote>\n",
    "给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数。\n",
    "例子：\n",
    "    \n",
    "    输入：nums = [2,7,11,15], target = 9\n",
    "    输出：[2,7]\n",
    "    解释：因为 nums[0] + nums[1] == 9 ，返回 [2, 7] 。\n",
    "</blockquote>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "partial-cornell",
   "metadata": {},
   "source": [
    "本练习在上一节中我们已经实现过，思路是通过两重 for-in 循环寻找两个和为target的整数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "cooked-filename",
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_sum(num1, num2, target):\n",
    "    a = num1\n",
    "    b = num2\n",
    "    return a + b == target\n",
    "\n",
    "def twosum(nums, target):\n",
    "    finded = False\n",
    "    for a in nums:\n",
    "        for b in nums:\n",
    "            if check_sum(a,b,target):\n",
    "                return [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "pointed-familiar",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 7]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,7,11,15]\n",
    "twosum(nums, 9)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "stretch-andrews",
   "metadata": {},
   "source": [
    "在这里我们简要引入时间复杂度的概念，它在计算机科学与数据科学领域发挥着不可替代的作用。我们经常会看到 $O(n),O(log(n)),O(n^k)$ 等符号，它们表示程序运行时间与程序输入大小的关系。\n",
    "\n",
    "其中 $O(n)$ 表示程序运行时间跟随程序输入大小线性增长。就好比我们在赛百味买一个 6 英寸三明治是 18 块钱，买一个 12 英寸的三明治是 36 块钱……\n",
    "\n",
    "$O(n^2)$ 表示程序运行时间跟随程序输入大小平方增长。就像我们在必胜客买一个 12 英寸的披萨的价格大概是 6 英寸披萨价格的四倍……"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "behavioral-farming",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Text(0, 0.5, 'Running time')"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEJCAYAAACT/UyFAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAluklEQVR4nO3deXyU5bn/8c+VELKwJiFAgIRNFHFDjSsqUnfUilVUxN1zqL9qq1Z/am1Ptfac1tOq1V9rtbgvKCJuVFGx1LUVFRABRUUBCYvsW0gIWa7fH88ACSRhEjLzJDPf9+s1r2SGmXmuUfLlzv3cz3WbuyMiIskjJewCREQkvhT8IiJJRsEvIpJkFPwiIklGwS8ikmQU/CIiSSZmwW9mBWb2tpnNM7PPzezayOO3m9lSM5sVuQ2PVQ0iIrIri9U6fjPLB/LdfaaZdQBmACOA84ASd78rJgcWEZEGtYnVG7v7cmB55PtNZjYP6NmU9+rSpYv36dOnGasTEUl8M2bMWO3ueTs/HrPgr8nM+gAHAx8BQ4BrzOwSYDpwg7uva+j1ffr0Yfr06TGvU0QkkZjZd3U9HvOTu2bWHngBuM7dNwIPAP2BwQS/Edxdz+vGmNl0M5u+atWqWJcpIpI0Yhr8ZpZGEPrj3P1FAHdf4e5V7l4NPAQcXtdr3X2suxe5e1Fe3i6/qYiISBPFclWPAY8A89z9nhqP59d42tnA3FjVICIiu4rlHP8Q4GJgjpnNijx2KzDKzAYDDiwCfhzDGkREZCexXNXzAWB1/NHkWB1TRER2T1fuiogkGQW/iEiSUfCLiLREFWUw+SbYvKbZ31rBLyLS0rjDqz+Hj/8Gyz5t9rdX8IuItDQzHoPPnoHjboIBJzb72yv4RURakqUz4PWbof8JcPwtMTmEgl9EpKXYvAaeuwTad4dzHoaU1JgcJi5N2kREZDeqq+CFK2HzSrjiTcjKidmhFPwiIi3BO7+HBW/DmfdBz0NieihN9YiIhO2rN+C9P8LBF8Ehl8b8cAp+EZEwrV0IL42B7gfC8LvA6up007wU/CIiYdm6GZ67CDA4/ylIy4zLYTXHLyISBneY9DNY8TmMngjZfeJ2aI34RUTC8OH9MHcinPBfMblIqyEKfhGReFv4Hrz1a9j3TDjm53E/vIJfRCSe1hfD85dB7l4w4oG4nMzdmYJfRCReKsqCk7lVFXDBOEjvEEoZOrkrIhIP7vDaDbB8FlzwLHQZEFopGvGLiMTDJw/DrHEw9GYYODzUUhT8IiKxtugDeOMWGHAKDI1Nx83GUPCLiMTS+sUw4RLI7gvnPAQp4cdu+BWIiCSqrZth/IVQVQmjnoWMTmFXBOjkrohIbLjDK9fA93PhwgmhnszdmUb8IiKx8MGf4PMX4cTbYO+Tw66mFgW/iEhz+/pNmHoH7H8ODLku7Gp2oeAXEWlOq76GF/4Duh8AP/xLKFfm7o6CX0SkuZStg/GjILUtXPAMtM0Ku6I66eSuiEhzqKqE5y+Hdd/BpZOgc0HYFdVLwS8i0hym/DLYM/eHf4beR4ddTYM01SMisqemPwYfPQhHXg2HXBJ2Nbul4BcR2RML34fJN8JeJ8JJd4RdTVQU/CIiTbV2IUy4GHL6wbmPQmrrmD2PWfCbWYGZvW1m88zsczO7NvJ4jpm9ZWbzI1+zY1WDiEjMbNkIz14QXKE7anyLaccQjViO+CuBG9x9X+BI4GozGwTcAkx19wHA1Mh9EZHWo7oqWKu/ej6c9yTk9g+7okaJWfC7+3J3nxn5fhMwD+gJnAU8EXnaE8CIWNUgIhITU/4L5r8Jw/8A/YaGXU2jxWWO38z6AAcDHwHd3H05BP84AF3jUYOISLOY/ihMux+OuAoO+4+wq2mSmAe/mbUHXgCuc/eNjXjdGDObbmbTV61aFbsCRUSi9e0/4bUbYcDJcMrvwq6myWIa/GaWRhD649z9xcjDK8wsP/Ln+cDKul7r7mPdvcjdi/Ly8mJZpojI7q36CiZcBnkDgxU8KalhV9RksVzVY8AjwDx3v6fGH00CLo18fynwSqxqEBFpFptXw7iR0CYdLnwO0juEXdEeieWi0yHAxcAcM5sVeexW4E5ggpldCSwGRsawBhGRPVNZDuNHQ8kKuGxyi+7BE62YBb+7fwDU14/0hFgdV0Sk2bjDpJ9C8TQY+Tj0OjTsipqFrtwVEanPu/8Ls5+DH/wK9js77GqajYJfRKQus56Bd34Pg0fDsTeGXU2zUvCLiOxswbvBFE/foXDGvS1yF609oeAXEalp5Zfw3MWQOyBox9CmbdgVNTsFv4jINptWBMs20zJg9ATI7Bx2RTHROnqIiojE2tbN8Oz5ULoaLp8MnQvDrihmFPwiItu6bS7/LNgkvcfBYVcUUwp+EUlu7vDGLfDVZBh+F+xzWtgVxZzm+EUkuf3rPvh4LBx1DRz+n2FXExcKfhFJXrMnwD9ug/3PgZN+G3Y1caPgF5HktOAdePkn0OdYGPEApCRPHCbPJxUR2eb7OTD+IugyAM5/Oui6mUQU/CKSXNYvhqfPhYyOMHpiwq7Vb4hW9YhI8ihdG4R+RRlc8QZ06hl2RaFQ8ItIcqgog/EXwrqFcPFL0G1Q2BWFRsEvIomvqhImXgGLp8HIx6DPMWFXFCoFv4gkNnd49dodF2glUF/9ptLJXRFJbFPvgE+fhuNuSpoLtHZHwS8iiWvaA/DBPXDoZTDs1rCraTEU/CKSmOZMDHrw7HsmnH5Pwm2msicU/CKSeL6ZCi9dBb2PgR89DCmpYVfUoij4RSSxFH8S7KCVNxBGPRNsqiK1KPhFJHGs+BzGnQvtu8JFL0BGp7ArapEU/CKSGNYuhKfOhrRMuOQV6NAt7IpaLK3jF5HWb+NyePIsqNoKl78B2b3DrqhFU/CLSOtWuhae/hGUroFLJkHXgWFX1OIp+EWk9SovgXEjYc23MPp56HVo2BW1Cgp+EWmdKrbAc6Nh2adw/lPQb2jYFbUaCn4RaX2qKmDi5cEuWiMegIGnh11RqxLVqh4zyzSzfWJdjIjIblVXwYtjdjRdG3xh2BW1OrsNfjM7E5gFvBG5P9jMJsW4LhGRXVVXw6Sfwecvwkl3qOlaE0Uz4r8dOBxYD+Dus4A+sSpIRKRO7vDGzTDraRh6Mwy5NuyKWq1ogr/S3TfEvBIRkfq4wz9uh4/HwlHXwPG/CLuiVi2a4J9rZhcCqWY2wMz+DPx7dy8ys0fNbKWZza3x2O1mttTMZkVuw/egdhFJFu/fBf+6F4qugJP/W50291A0wf9TYD+gHHgW2AhcF8XrHgdOrePxP7n74MhtcpR1ikiy+vdf4J//DQdeAMPvVug3g90u53T3UuCXkVvU3P09M+vTxLpERGDagzDllzBoBJx1P6SovVhziGZVT5GZvWhmM81s9rbbHhzzmsh7PGpm2Q0cd4yZTTez6atWrdqDw4lIq/TJw8HJ3IFnwDkPQ6ouO2ou0fzzOY5g2uYc4Mwat6Z4AOgPDAaWA3fX90R3H+vuRe5elJeX18TDiUirNONxeO0G2Ps0OPcxSE0Lu6KEEs0/oavcvVnW7bv7im3fm9lDwKvN8b4ikkA+HQd/vw72OgnOewLatA27ooQTTfDfZmYPA1MJTvAC4O4vNvZgZpbv7ssjd88G5jb0fBFJMp89B69cDf2Oh/OfhjbpYVeUkKIJ/suBgUAaUB15zIEGg9/MngWOB7qY2RLgNuB4Mxscef0i4MdNKVpEEtCcifDyVdDnGLhAWybGUjTBf5C7H9DYN3b3UXU8/Ehj30dEksDs5+GlMVB4FFz4HLTNCruihBbNyd1pZjYo5pWISHKaPSES+kfDhROgbbuwK0p40Yz4jwEuNbOFBHP8Bri7HxjTykQk8X32XDC903tIZKSv0I+HaIK/rqtvRUT2zGfj4aXInL5CP67qDX4z6+juG4FNcaxHRJLBrGfg5Z9A32NhlOb0462hEf8zwBnADIJVODUbZDjQL4Z1iUii+nRcZMnmULjgWYV+COoNfnc/I/K1b/zKEZGENv0xePU66DcMRj0LaZlhV5SUounVMzWax0REGjTtwSD0B5wMo8Yr9EPU0Bx/BpBFcAFWNjumejoCPeJQm4gkig/uhX/cFjRcO/cxtWEIWUNz/D8m6Lvfg2Cef1vwbwTuj21ZIpIQ3OHdP8A7v4P9z4Gz/6aGay1AQ3P89wH3mdlP3f3PcaxJRBKBO0y9Az64Bw66EM76C6Skhl2VEN1GLAp9EWkcd3jzlzDtfjj0Mjj9T9pEpQXRzgYi0ryqq4KTuDOfhCOuglPv1HaJLYyCX0SaT+VWeOnH8PmLcOyN8INfKfRboN0Gv5kdUsfDG4Dv3L2y+UsSkVapogwmXALzp8BJd8CQa8OuSOoRzYj/r8AhwGyClT37R77PNbOr3H1KDOsTkdZgy0Z4dhR89y84414oujzsiqQB0ZxtWQQcHNn/9lDgYIKds04E/hDD2kSkNShdC0/+EIqnBZuiK/RbvGhG/APd/fNtd9z9CzM72N0XmObuRJLbxmXw1I9g7QI4fxzso2a+rUE0wf+VmT0AjI/cPx/42szSgYqYVSYiLdvqb+Cps6FsLVw0EfoeF3ZFEqVogv8y4CcEV/Ea8AFwI0HoD4tVYSLSgi2dCePOBQwuexV6HBx2RdII0VzAVQbcHbntrKTZKxKRlm3BOzB+NGTlwMUvQ27/sCuSRopmOecQ4Hagd83nu7v68Yskm89fghfHQO5ecNGL0DE/7IqkCaKZ6nkEuJ6gUVtVbMsRkRbrk4fhtRuh4Ai4cDxkZoddkTRRNMG/wd1fj3klItIyucM7d8K7d8KAU2Dk49o1q5WLJvjfNrM/Ai8C5dsedPeZMatKRFqGqoqg786nT8Pg0XDmfWqrnACiCf4jIl+LajzmwA+avxwRaTHKS+D5y+Cbt+C4m2DYreq7kyCiWdWjJZsiyaZkJTxzHiz/TC0YElBDWy9e5O5Pm9nP6/pzd78ndmWJSGjWfAtP/wg2rYALnoF9Tgu7ImlmDY3420W+dohHISLSAiyZHoz0Ibgwq1dRw8+XVqmhrRf/Fvn6m/iVIyKh+eKVYI1+h+7BGn1dmJWwormAKw/4T6APtS/guiJ2ZYlI3LjDv/8Mb/0aeh0Go56Fdl3CrkpiKJpVPa8A7wP/QBdwiSSWqkqYfCPMeAwGjYCzH4S0zLCrkhiLJviz3P3mmFciIvG1ZWOwXPPbqXDM9fCDX2tD9CQRzf/lV81seGPf2MweNbOVZja3xmM5ZvaWmc2PfNU13yJh2LAEHj01aLh25n1w4u0K/SQSzf/pawnCv8zMNprZJjPbGMXrHgd23pXhFmCquw8Apkbui0g8LZkBD50AG4qDPvqHXhZ2RRJnuw1+d+/g7inununuHSP3O0bxuveAtTs9fBbwROT7J4ARjS1YRPbA3Bfg8eHQpi1c8Sb01wX4ySiaOX7MrCe7tmV+rwnH6+buyyOvX25mXZvwHiLSWNXV8O7/Bo3WCo+C85/Wyp0kFs1yzv8l2G7xC3as6nGgKcEfNTMbA4wBKCwsjOWhRBLb1lJ45SdBL/3Bo+GMP0Gb9LCrkhBFM+IfAezj7uW7e2IUVphZfmS0nw+srO+J7j4WGAtQVFTkzXBskeSzcTmMHwXLZsFJd8DRP1OjNYnq5O4CoLn6sE4CLo18fynBNQIiEgtLZsBDw2D1/OCirCHXKvQFiG7EXwrMMrOp1O7H/7OGXmRmzwLHA13MbAlwG3AnMMHMrgQWAyObWLeINGTWM/D366BDt+Akbvf9w65IWpBogn9S5NYo7j6qnj86obHvJSJRqqqEKb+Cjx6AvsfByCeCTdFFaoimH/8Tu3uOiLQAm9fAxMtg4Xtw5E/gpN9CalQL9yTJRLOqZyHBKp5a3L1fTCoSkcb7fm5wEnfTChjxIAyu7xdukeimemo25M4gmJfX744iLcWciTDpp5DRGS5/HXodGnZF0sJFc+Xumhq3pe5+L9pvVyR8VRXwxi/ghSuh+4Ew5h2FvkQlmqmeQ2rcTSH4DUC7comEadP3QWfNxR/CEf8HTv4tpDbXqmtJdNFM9dxd4/tKYBFahikSnu8+hOcvhfJNcM4jcMC5YVckrUw0q3qG1bxvZm0IWjh8HauiRKQO7vDRg8Fyzc694eKXodugsKuSVqjeOX4z62hmvzCzv5jZSRa4BvgGOC9+JYoIWzbCxMvhjVtgwCkw5m2FvjRZQyP+p4B1wIcEe+7eBLQFRrj7rNiXJiIAfD8HJlwK6xbBCbfBkOu0aYrskYaCv5+7HwBgZg8Dq4FCd98Ul8pEkp07zHwCJt8UXH172avQ++iwq5IE0FDwV2z7xt2rzGyhQl8kTspL4LWfw+znoN8w+NFD0D4v7KokQTQU/AfV2GLRgMzIfQM8ml24RKQJVs4LpnZWfw3DfgnH3gApqWFXJQmk3uB3d/1NE4knd5jxeHBRVnoHuOQV6Dc07KokAamDk0hLULYOJv0M5k0KpnbO/lvQUlkkBhT8ImFbPA1e+A/YtDzYJeuon2rVjsSUgl8kLNVV8P7d8M7voXMhXDkFeqrXjsSegl8kDOuL4aWr4LsP4ICRcPo9kKH1EhIfCn6ReJv9PLx2A3gVnPVXGHyh9sKVuFLwi8RL2fog8OdOhIIjghO4OX3DrkqSkIJfJB4Wvgcv/R8o+R6G/QqOuV7bIkpo9DdPJJYqtsDb/wP//jPk9tcJXGkRFPwisbLs0+AE7qov4dDL4ZT/gbbtwq5KRMEv0uwqt8L7d8F7d0H7rjB6Igw4KeyqRLZT8Is0p+/nwstXBa2UDxoFp/4eMrPDrkqkFgW/SHOoqoR/3Qvv3AmZneGCZ2Dg6WFXJVInBb/Invp+DrxyNSz/DPY7G4bfDe1yw65KpF4KfpGmqtgC7/0xGOln5sDIJ2C/EWFXJbJbCn6Rplj8EUy6JuiZf9CFwYqdrJywqxKJioJfpDHKS2DqHfDxWOjUCy56AfY6MeyqRBpFwS8SrS9fC/a/3bgUDv9POOHXwYYpIq2Mgl9kdzYsgddvhi9fha6D4NxHoPDIsKsSaTIFv0h9qiqDKZ23/yfonX/i7XDUNZCaFnZlInsklOA3s0XAJqAKqHT3ojDqEKnX0hnw9+vg+9kw4GQY/kfI7hN2VSLNIswR/zB3Xx3i8UV2tXkNTP0NzHwS2ncLlmgOOkv98iWhaKpHBIKpnBmPwz9/C1s2wlFXw9CbtSuWJKSwgt+BKWbmwN/cfWxIdYhA8Scw+Ybgyts+xwbTOl33DbsqSXIl5ZUUry2lICeL9unNG9VhBf8Qd19mZl2Bt8zsS3d/r+YTzGwMMAagsLAwjBol0W1aEazJn/U0dMiHcx6B/c/RtI7ERVW18/3GLSxeU0rx2lIW17gVry1lzeatADxxxeEM3TuvWY8dSvC7+7LI15Vm9hJwOPDeTs8ZC4wFKCoq8rgXKYmrYgtMux/evwcqy+Hon8HQm7QmX5rdxi0V9Qb70vVlVFTtiLbUFKNn50wKc7I4eb/uFOZkUZiTxaD85p9ujHvwm1k7IMXdN0W+Pxm4I951SBJyhy9ehim/hg2LYeAZcNIdwc5YIk1QUVXN8vVbgjBfVzvYF68tZX1pRa3nd8pMo3duFvv17MRpB+RvD/eC7Cx6dM6gTWpKXOoOY8TfDXjJgl+n2wDPuPsbIdQhyWTpTHjzVlj8IXTbH86aBP2Ghl2VtHDuzoayil1G69u+X7Z+C1XVO0btaamRUXtuOw7s1WlHsEduHTNaxjUgcQ9+d18AHBTv40qSWrcIpv4W5k6Ednlw5v+Dgy+ClNSwK5MWYmtlNUvXl9UK9prhvmlLZa3n57ZrS0FOFoMLsjnroB3BXpibRfeOGaSmtPxzRFrOKYlp85pg+8OPH4KUNnDMz+GY67U8Mwm5O2s3b61zxF68toxlG8rwGmcR27ZJoSA7mGsv6p0dhHok2Auys2jXzCtswtD6P4FITVtL4aMH4IN7YWsJDB4Nw26Fjj3CrkxiaEtF1fZRe/HaUhavqT01s3lrVa3n53VIpzAni8P75mwP9oLsTHrntqNrh3RSWsGofU8o+CUxVFXAp0/Du3+ATctg79PgxNu0Hj9BuDurNpXvOIG6ZkfIF68r5fuNW2qN2jPSUrbPrx/VP3f7CdRto/bMtsk91afgl9atugpmT4B37wzm83sdBuc8DH2GhF2ZNFLZ1qog2NfseiK1eF0pWyqqtz/XDLp3zKAgO4she3WJhHrm9vn2vPbpmK7HqJeCX1qn6mqY9wq8/btgF6zuB8CFE4KGavqBb5Gqq52Vm8rrXSGzalN5ree3a5tKQU4Wfbu047i98+idm7V9WqZn50wy0pJ71L4nFPzSurjDV6/DO78LNjnvsg+c9yQMPBNS4rMGWuq3ubyy1qi91onUdWVsraw9au/RKZOCnEyG7ZO3Y3VM5JbTrq1G7TGi4JfWoboavvw7vPtHWDEHsvvC2WPhgHO1NDOO6mszULwuuL+6ZGut53fIaENhThZ7d+vAift2276evSA7k17ZWbRto3+sw6Dgl5atugo+fwneuwtWzYPcvWDEg3DASEjVX99YaGybgR6dM+id046TBu1oMxCM3jPpnNU2xE8i9dFPjrRMVRUwZyK8fzesmQ95A4MmavudrRH+Hqqsqmb5hi21Qr2hNgOds9IozMlivx612wwU5mSR3yl+bQak+Sj4pWUpL4GZT8CHf4WNS4L2CiOfgH1/qDn8KNVsM1C8tmyXYF+6vqxWm4E2KUav7EwKcrI4/YB8CnKy6F2jzUCnzJbRZkCaj4JfWoaSVfDx34Irbbesh97HwJn3wl4napVOHWq2Gdi5xUDDbQY6c+ZB+bXWted3ymwVbQak+Sj4JVyr58O0B2DWuKBF8sDTg9YKvZJ7G+bdtRlYvqGM6t20GSioEe7NvZGHtG762yDx5w7f/jMI/G/egtS2cOD5MORa6DIg7OripryyiiXrGtdmoCA7s1abgW23ZGgzIM1HwS/xs7UUZj8HHz0Iq76Edl3h+Fuh6HJo3zXs6pqdu7OqpHzHaH1bm4HI0se62gwUZAdBfmS/3B3BnptFr+xMstrqx1Wah/4mSeyt+RZmPBb00ilbF1xlO+JB2P9H0CY97Or2yLY2A8V1rI5ZvLZ2mwEI2gwU5mRxdP8uFORk0js3S20GJO4U/BIbVZXw9Rsw/ZFgWsdSg/n7I66C3ke3mhO2jW0zkNU2lcKcLPrktuO4AXnbm4IV5ASjdrUZkJZAwS/Na+OyYGQ/43HYuBQ69Aimcw65BDrmh11dnUrKK3c0A4uizUB+xwwKc7N2aTNQkJNFrtoMSCug4Jc9V7kVvn49CPxv/gFeDf2GwWl/gL1PDf0K2/raDGwL+jWbd2ozkN6GwtwsBnQN2gz0qnEStUfnDNLbaNQurZuCX5pu5TyY+RTMHg+la6BDfrAUc/DouG9gvnFLRR3r2csoXlvKknWldbYZKMzJ4qRB3SjMrb1CplNmmkbtktAU/NI4m1bA3BdgzgRY9imkpME+p8HBF8NeJ8SsncLObQaKd/q6rp42A4N6dOSU/boHJ1Jz2gVtBjpnkKY2A5LEFPyye+Wb4MvXgqWYC94JpnLyD4JTfhesv2/XZY8P0dg2A2mpRq/s4ITp8Br9Y9RmQGT3FPxSt62lwXz9Fy/Dl5Ohsgw6Fwablh94HuTt0/i3rKxm2fpdQ72hNgO9Im0GfnhQjx0nUnOz6N4xQ20GRJpIwS87bC2F+VOCsP96ClRshqxcGDwqGNkXHNHgMkx3Z11pRe1gr3E16i5tBlJT6JWTSUF2Fof2zt5lhYzaDIjEhn6ykl3p2mBk/+VrQehXlEJWl2BUv9+IoFlajVU5NdsMLKnjRGpJee1Re16HdApzsjisTzYFOT1rXY3arUOG2gyIhEDBn4zWLgi2L/zqdfju3+BVQfuEgy7AB53FqtwiitdHGoS9vXC3bQa2hfmR/XJqdX1UmwGRlkk/lcmgYgt896/gCtr5b8HqrwDY1GkfFvS5nI/Tj+TjLYV8N38LxR+VUVbxbq2Xd+uYTu+cdhzdv0tktJ65PeDzOqjNgEhro+BPQNVV1az5bi6l86aQvuhtuqz5hDbV5VTQhk9tXyZXXMI/qg9hyYqusCJoM1CQXU7v3HYcOyCv1goZtRkQSTwK/lZqc3klxesiJ0/XbGbz9/Pp+P00CjbO4ICKOXSzdQB8W53P69XH83nmYazKLaJrbjAd839zd5xIVZsBkeSi4G+hGmozsGRNCdllizg05WsOT/mS4Slf0MPWArAhNZuluUUs7H4kttcJdC3cm9GdM2nbRhcsiUhAwR+iTVsq6ljPvmubgfaUckjqtwzNWsiVKfPZm6/ITC8BoCKjC977WLz/cVjf4+jUZQCdNHoXkQYo+GOosW0GOmWmsU/nas7qtJQDcxbSr+IbupXMI3PTouAJFQZdB0HByGBNfcHhpOX0azUtjkWkZVDw76ENNS5Y2l2bgTYpRq/sTApysjhj/zwOyFjFAIrpWbGI7JJvSFs9D9YthHWRF3TsBT0HQ/5F0POQYB/ajE6hfE4RSRyhBL+ZnQrcB6QCD7v7nWHUEY1tbQaK19WxEceaUjbW0WagINJm4MwDuzOgfRn9U1fSs2opncuKSVn7Laz5BubOh+rIiN9Sg26W3Q+Ag0dD/sHQY3Cz9MAREdlZ3IPfzFKB+4GTgCXAJ2Y2yd2/iHct0PQ2A4U5WRzWqz0D2m+hb9sNFKSsJq96FeklS2HDElhfDIsWQ/nGHS9OaQPZfYOQ3/uUYNqm676QOwDSMuL/4UUkKYUx4j8c+MbdFwCY2XjgLCBmwb+looqlkeZgOwf7krUlVG0tI5OtZFJOppVTmLWV/dtXMjx7K73yy+maVkZOaimdqjeQWb4G27wSVq6A79bterD0TtC5ADr1CrYYzOkPuXtBbj/oVBj6piQiImGkUE+guMb9JcARsTjQh4/eTH7x3/GqStKoZoA5+1JFKtWkp1STzlbSU8ph58F2FbAhctumbYdg6qV9V+gyAPocA+27Qbu8YAOSbWGvOXgRaeHCCP66lqD4Lk8yGwOMASgsLGzSgdp06s769XuTmd6WzPR0MjLa0i4jnYz0tlhKG2ibBWlZkJZZ42tmEN4Z2ZDZGTI6B/c1UheRBBFGmi0BCmrc7wUs2/lJ7j4WGAtQVFS0yz8M0TjsnOuB65vyUhGRhBXG5ZyfAAPMrK+ZtQUuACaFUIeISFKK+4jf3SvN7BrgTYLlnI+6++fxrkNEJFmFMnHt7pOByWEcW0Qk2alzl4hIklHwi4gkGQW/iEiSUfCLiCQZBb+ISJIx9yZdGxVXZrYK+K6JL+8CrG7GcloLfe7kk6yfXZ+7fr3dPW/nB1tF8O8JM5vu7kVh1xFv+tzJJ1k/uz5342mqR0QkySj4RUSSTDIE/9iwCwiJPnfySdbPrs/dSAk/xy8iIrUlw4hfRERqSOjgN7NTzewrM/vGzG4Ju554MLNHzWylmc0Nu5Z4MrMCM3vbzOaZ2edmdm3YNcWDmWWY2cdm9lnkc/8m7JriycxSzexTM3s17FrixcwWmdkcM5tlZtOb9B6JOtUT2dT9a2ps6g6MCmtT93gxs+OAEuBJd98/7HrixczygXx3n2lmHYAZwIgk+P9tQDt3LzGzNOAD4Fp3nxZyaXFhZj8HioCO7n5G2PXEg5ktAorcvcnXLiTyiH/7pu7uvhXYtql7QnP394C1YdcRb+6+3N1nRr7fBMwj2N85oXmgJHI3LXJLzNHcTsysF3A68HDYtbQ2iRz8dW3qnvBBIGBmfYCDgY9CLiUuItMds4CVwFvunhSfG7gXuAmoDrmOeHNgipnNiOxN3miJHPxRbeouicXM2gMvANe5+8aw64kHd69y98EE+1cfbmYJP8VnZmcAK919Rti1hGCIux8CnAZcHZnebZREDv6oNnWXxBGZ434BGOfuL4ZdT7y5+3rgHeDUcCuJiyHADyPz3eOBH5jZ0+GWFB/uvizydSXwEsG0dqMkcvBrU/ckEjnJ+Qgwz93vCbueeDGzPDPrHPk+EzgR+DLUouLA3X/h7r3cvQ/Bz/Y/3f2ikMuKOTNrF1m8gJm1A04GGr2CL2GD390rgW2bus8DJiTDpu5m9izwIbCPmS0xsyvDrilOhgAXE4z8ZkVuw8MuKg7ygbfNbDbBYOctd0+apY1JqBvwgZl9BnwMvObubzT2TRJ2OaeIiNQtYUf8IiJSNwW/iEiSUfCLiCQZBb+ISJJR8IuIJBkFvyQ0MyvZ/bP2+Bi3NvL5d5jZibGqR2R3tJxTEpqZlbh7+9Z+DJHmpBG/JAUzO97M3jWzCWb2tZndaWajI73s55hZ/8jzHjezB83s/cjzzog8fpmZ/aXG+70aec87gczIBWPjdjpmauT95kaOcX2NY5xrZkU1LjabY2Ye+fP+ZvZGpAnX+2Y2MG7/oSQptAm7AJE4OgjYl6Bt9QLgYXc/PLJpy0+B6yLP6wMMBfoTXBW7V31v6O63mNk1kSZpOxsM9Ny2L8K21go1Xjs98hzM7I/AtiswxwJXuft8MzsC+Cvwg8Z9VJH6KfglmXzi7ssBzOxbYErk8TnAsBrPm+Du1cB8M1sANHXEvQDoZ2Z/Bl6rcbxazOw84BDg5Eh30aOB54P2QwCkN/H4InVS8EsyKa/xfXWN+9XU/lnY+cSXA5XUnhrN2N3B3H2dmR0EnAJcDZwHXFHzOWa2H/Ab4Dh3rzKzFGB9Pb9BiDQLzfGL7GqkmaVE5v37AV8Bi4DBkccLqN0KtyLSEroWM+sCpLj7C8B/EYzqa/55J4KWwpe4+yqAyB4CC81sZOQ5FvnHQ6TZaMQvsquvgHcJOiFe5e5bzOxfwEKCaaG5wMwazx8LzDazme4+usbjPYHHIqN4gF/sdJwRQG/goW3TOpGR/mjgATP7FcFWiuOBz5rt00nS03JOkRrM7HHgVXefGHYtIrGiqR4RkSSjEb+ISJLRiF9EJMko+EVEkoyCX0QkySj4RUSSjIJfRCTJKPhFRJLM/wf7aFzqMi51kQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "## 本段代码绘图使用无需理解\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt \n",
    "x = np.arange(0,5,0.1)\n",
    "y = x\n",
    "plt.plot(x,y)\n",
    "y = x**2\n",
    "plt.plot(x,y)\n",
    "plt.xlabel('Imput size')\n",
    "plt.ylabel('Running time')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "brilliant-radical",
   "metadata": {},
   "source": [
    "在上面的图中可以直观看到 平方复杂度 随着时间增长 运行时间急剧增加，因此能够把复杂度从 $O(n^2)$ 降低到 $O(n)$ 甚至 $O(log(n))$ 带来的增益是巨大的。尤其是在数据科学领域，程序往往需要处理上千万条数据，不同复杂度的代码运行时间差距非常显著。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "brief-oakland",
   "metadata": {},
   "source": [
    "那么在上述程序中，输入序列的大小为 4，在最坏情况下 twosum 函数中的两个 for-in 循环一共执行 16 次 check_sum 操作，因此该算法的复杂度是$O(n^2)$。下面我们用 字典 优化代码复杂度为 $O(n)$，思路是遍历一次序列并将遍历过的元素值存储到字典中，若有字典中的元素值与序列中的元素值求和为target，则返回这两个值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "fewer-income",
   "metadata": {},
   "outputs": [],
   "source": [
    "def twosum(nums, target):\n",
    "    hashtable = {}\n",
    "    for num in nums:\n",
    "        if num in hashtable:\n",
    "            return [hashtable[num], num]\n",
    "        hashtable[target - num] = num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "hearing-latter",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 7]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "twosum(nums,9)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.2"
  },
  "notify_time": "10",
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "189.25271606445312px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
